package Midium;

import java.util.ArrayList;
import java.util.List;

//22.括号生成
/*
输入：n = 3
输出：[
       "((()))",  111000  初始
       "(()())",  110100  2和3交换位置（循环开始3==n）
       "(())()",  110010  2和4交换位置（循环截止4 == 2*3-2）
       "()(())",  101100  1和3交换位置
       "()()()"   101010  1和4交换位置
                  100 不存在
     ]

输入：n = 4
输出：[
        外层循环开始4-1＝3，循环截止1
        循环开始n=4 循环截止2*4-2=6
        f(1)='('或')'
        f(2)="()"
        f(p)=f(1)+f(p-1),f(p-1)需要知道f(1)是左还是右,其中,p>=3

        "(((())))",  11110000    f(1)+f(7),其中f(1)='(',f(7)=f(1)+f(6).
        "((()()))",  11101000
        "((())())",  11100100
        "((()))()",  11100010
        "(()(()))",  11011000
        "(()()())",  11010100
        "(()())()",  11010010
        "(())(())",  11001100
        "(())()()",  11001010
        "()((()))",  10111000
        "()(()())",  10110100
        "()(())()",  10110010
        "()()(())",  10101100
        "()()()()"   10101010
        ]
         f(8,4)=['('+f(7,3)]+[')'+f(7,4)]  f的第二个参数为还需要的左括号个数
          显然，')'+f(7,4) 这种情况是不合理的，因此增加约束条件，对于f(p,q)，需有p-q >= q,p初始为2*n
          即.还需要的右括号的个数需要大于等于还需要的左括号的个数
          f(7,3)=['('+f(6,2)]+[')'+f(6,3)]
          f(6,2)=['('+f(5,1)]+[')'+f(5,2)]
          f(6,3)=['('+f(5,2)]+[')'+f(5,3)]
          ...
          f(p,q)=['('+f(p-1,q-1)]+[')'+f(p-1,q)]
 */
public class Solution22 {
    public static void f(List<String> list,String s, int p, int q,int n) {
        if(p-q < q)
            return ;
        if(q==0){
            for(int i = p ;i > 0 ; i--)
                s+=")";
            list.add(s);
            return;
        }
        String str1 = s+"(";
        f(list,str1,p-1,q-1,n);
        String str2 = s+")";
        f(list,str2,p-1,q,n);
    }

    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        f(list,"",2*n,n,n);
        return list;
    }

    public static void main(String[] args) {
        List<String> list = generateParenthesis(3);
        for (String str :
                list) {
            System.out.println(str);
        }
    }
}
